#include <iostream>
using namespace std;

class Solution {
public:
    int climbStairs(int n) {
        if( n == 0 || n ==1 || n == 2 )
            return n;
    
        int *step = new int[n];
        step[0] = 1;
        step[1] = 2;
        for( int i = 2; i < n; i++ )
            step[i] = step[i -2] + step[i - 1];

        int tmp = step[n-1];
        delete[] step;
        return tmp;
    }
};

int main(int argc, const char *argv[]){
    Solution a;
    cout << a.climbStairs(4) << endl;
    return 0;
}

